package com.LC._74;

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        if(target<matrix[0][0]||target>matrix[matrix.length-1][matrix[0].length-1]){
            return false;
        }
        int i=0;
        if(matrix.length>1){
            for( i=0;i<matrix.length;){
                if(matrix[i][0]<=target && target <= matrix[i][matrix[0].length-1]){
                    break;
                }else if(i<matrix.length){
                    i++;
                }else{
                    return false;
                }

            }
        }
        // if(i>matrix[0].length-1){
        //     return false;
        // }
        int left =0;
        int right= matrix[0].length-1;
        while(left<=right){
            int mid = left + (right-left)/2;
            // if(mid>matrix[0].length){
            //     return false;
            // }
            if(matrix[i][mid]==target){
                return true;
            }
            if(matrix[i][mid]<target){
                left = mid +1;
            }else{
                right = mid-1;
            }
        }
        return false;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        int target=2;
        int[][] nums = new int[][]{
//                {1,3,5,7},{10,11,16,20},{23,30,34,60}
                {1},{3}
        };
        System.out.println(solution.searchMatrix(nums , target));
    }
}
